/*
 * @Author: liusheng
 * @Date: 2022-05-19 22:58:07
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-20 17:58:49
 * @Description: 剑指 Offer II 066. 单词之和
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 剑指 Offer II 066. 单词之和
实现一个 MapSum 类，支持两个方法，insert 和 sum：

MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
 

示例：

输入：
inputs = ["MapSum", "insert", "sum", "insert", "sum"]
inputs = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]

解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)
 

提示：

1 <= key.length, prefix.length <= 50
key 和 prefix 仅由小写英文字母组成
1 <= val <= 1000
最多调用 50 次 insert 和 sum
 

注意：本题与主站 677 题相同： https://leetcode-cn.com/problems/map-sum-pairs/

通过次数7,113 提交次数10,889
 */
#include "header.h"

class MapSum {
    map<string,int> stringWeight;
public:
    /** Initialize your data structure here. */
    MapSum() {

    }
    
    void insert(string key, int val) {
        stringWeight[key] = val;
    }
    
    int sum(string prefix) {
        if (prefix.empty())
        {
            return 0;
        }

        int n = prefix.size();
        auto gePrefix = stringWeight.lower_bound(prefix);
        int sum = 0;
        for (;gePrefix != stringWeight.end(); ++gePrefix)
        {
            if (gePrefix->first.substr(0,n) == prefix)
            {
                sum += gePrefix->second;
            }
            else
            {
                break;
            }
        }

        return sum;
    }
};

/*
We can remember the answer for all possible prefixes in a HashMap score. 
When we get a new (key, val) pair, we update every prefix of key appropriately: 
each prefix will be changed by delta = val - map[key], where map is the previous 
associated value of key (zero if undefined.)
*/
class MapSum {
    map<string,int> stringWeight;
    unordered_map<string,int> prefixSum;
public:
    /** Initialize your data structure here. */
    MapSum() {

    }
    
    void insert(string key, int val) {
        int delta = val;
        if (stringWeight.count(key))
        {
            delta = val - stringWeight[key];
        }

        stringWeight[key] = val;
        for (int i = 1; i <= key.size(); ++i)
        {
            prefixSum[key.substr(0,i)] += delta;
        }
    }
    
    int sum(string prefix) {
        return prefixSum[prefix];
    }
};

/*
same idea as above,but use Trie to keep trace the prefix Sum value
*/
class MapSum {
    class Trie 
    {
        array<Trie *,26> children;
        int val; // represent sum value
    public:
        Trie():children({nullptr}),val(0) {}

        void insert(const string & word,int delta)
        {
            Trie * node = this;
            for (char ch : word)
            {
                char chIndex = ch - 'a';
                if (!node->children[chIndex])
                {
                    node->children[chIndex] = new Trie();
                }
                node->val += delta;
                node = node->children[chIndex];
            }
            node->val += delta;
        }

        int getPrefixSum(const string & word)
        {
            Trie * node = this;
            for (auto ch : word)
            {
                char chIndex = ch - 'a';
                if (!node->children[chIndex])
                {
                    return 0;
                }
                node = node->children[chIndex];
            }
            return node->val;
        }
    };

    Trie * root;
    unordered_map<string,int> strWeight;
public:
    /** Initialize your data structure here. */
    MapSum() {
        root = new Trie();
    }
    
    void insert(string key, int val) {
        
        int delta = val;
        if (strWeight.count(key))
        {
            delta = val - strWeight[key];
        }
        strWeight[key] = val;
        root->insert(key,delta);
    }
    
    int sum(string prefix) {
        return root->getPrefixSum(prefix);
    }
};

